package L07.T01;

import com.sun.source.tree.Tree;

import java.util.ArrayList;
import java.util.List;

public class BinaryTree {
    static class TreeNode{
        public char val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(char val){
            this.val=val;
        }


    }

    public TreeNode root;

    //手动对树进行创建
    public TreeNode creatTree(){
        TreeNode A=new TreeNode ('A');
        TreeNode B=new TreeNode ('B');
        TreeNode C=new TreeNode ('C');
        TreeNode D=new TreeNode ('D');
        TreeNode E=new TreeNode ('E');
        TreeNode F=new TreeNode ('F');
        TreeNode G=new TreeNode ('G');
        TreeNode H=new TreeNode ('H');
        A.left=B;
        A.right=C;
        B.left=D;
        B.right=E;
        E.right=H;
        C.left=F;
        C.right=G;
        return A;
    }

    //二叉树的前序遍历
    public void preOrder(TreeNode root){
        if(root==null)return;
        System.out.print (root.val+" ");
        preOrder (root.left);
        preOrder (root.right);
    }
    //前序遍历的结果储存在list中
    public List<TreeNode> preOrder2(TreeNode root){
        List<TreeNode> ret=new ArrayList<> ();
        if(root==null) return ret;
        ret.add (root);
        //利用到了函数中的数组返回值
        List<TreeNode> leftTree=preOrder2 (root.left);
        ret.addAll (leftTree);
        List<TreeNode> rightTree=preOrder2 (root.right);
        ret.addAll (rightTree);
        return ret;
    }

    //中序遍历
    public void midOrder(TreeNode root){
        if(root==null)return;
        midOrder (root.left);
        System.out.print (root.val+" ");
        midOrder (root.right);
    }

    //后序遍历
    public void postOrder(TreeNode root){
        if(root==null)return;
        postOrder (root.left);
        postOrder (root.right);
        System.out.print (root.val+" ");
    }

    public int size=0;
    public void nodeSize(TreeNode root){
        //当返回值是int的时候，要写 return 0  ，void 的时候直接 return 没有问题
        if(root==null) return ;
        size++;
        nodeSize (root.left);
        nodeSize (root.right);
    }

    public int nodeSize2(TreeNode root){
        if(root==null)return 0;
        return nodeSize2 (root.left)+nodeSize2 (root.right)+1;
    }

    //计算叶子节点个数
    public int leafSize = 0;
    public void leafSize(TreeNode root){
        //计算二叉树某节点个数的思路：对二叉树进行遍历，加入判断条件，符合条件的自加
        if(root==null)return;
        if(root.left==null&&root.right==null) leafSize++;
        leafSize (root.left);
        leafSize (root.right);
    }

    public int leafSize2(TreeNode root){
        if(root==null)return 0;
        if(root.left==null&&root.right==null) return 1;
        return leafSize2 (root.left)+leafSize2 (root.right);
    }

    public int layerSize=0;
    //求树的第k层节点有多少个
    public int layerSize(TreeNode root,int k){
        //遍历树加上判断条件
        if(root==null)return 0;
        if(k==1)return 1;
        return layerSize (root.left,k-1)+layerSize (root.right,k-1);
    }

    public int getHeight(TreeNode root) {
        if (root == null) return 0;
        int a = getHeight (root.left);
        int b = getHeight (root.right);
        return a > b ? a + 1 : b + 1;
    }

    //二叉树对key值的查找
    public boolean findNode(TreeNode root,char key){
        if(root==null)return false;

        if(root.val==key)return true;
        boolean flag1=findNode (root.left,key);
        if(flag1) return true;

        boolean flag2=findNode (root.right,key);
        if(flag2) return true;

        return false;
    }


    //平衡二叉树：左右树的高度都不超过1

    public int getHeight2(TreeNode root) {
        if (root == null) return 0;
        int a = getHeight2 (root.left);
        int b = getHeight2 (root.right);

        //在高度计算过程中对二叉树的平衡进行判断

        //只有该二叉树是平衡二叉树的时候才允许返回树的高度
        //https://leetcode.cn/problems/balanced-binary-tree/submissions/
        if(a>=0&&b>=0&&Math.abs (a-b)<=1){
        return a > b ? a + 1 : b + 1;
        }else{
            return -1;
        }

    }

    public boolean isBalanced(TreeNode root) {
        if(root==null)return true;

        int num=getHeight2 (root);
        return num>=0;
    }

    public boolean isBalanced2(TreeNode root) {
        if(root==null)return true;

        int left=getHeight (root.left);
        int right=getHeight (root.right);


        //直接的写法，但这样会重复计算height，不够精简
        return Math.abs (left-right)<=1
                &&isBalanced2 (root.left)
                &&isBalanced2 (root.right);
    }

    //*************************************************
    //二叉树是否对称

    public boolean isSym(TreeNode p,TreeNode q){
        //所有的错误情况返回false
        if(p==null&&q!=null||p!=null&&q==null)return false;
        if(p==null&&q==null)return true;
        if(p.val!=q.val)return false;
        return isSym (p.right,q.left)&&isSym (p.left,q.right);
    }
    public boolean isSymmetric(TreeNode root) {
        if(root==null)return true;
        return isSym(root.left,root.right);
    }




}
